//
//  TCUTree.m
//  TreeMenuTest
//
//  Created by Etienne on 23/06/07.
//  Copyright (c) 2007 Etienne Samson. All rights reserved.
//

#import "TCUCFTree.h"

#import "CFRuntime_internal.h"

#import "TCUTree.h"

// This is a dictionary key reserved to hold our children when saved in plist form.
#define CODING_CHILDREN_KEY @"__children"
#define CODING_OBJECT_KEY @"__object"

@implementation TCUTree
/*"
TCUTree - Objective-C interface to CFTree
 
 TCUTree is a toll-free bridged class that provides an Objective-C interface to
 the CFTree opaque type and its functions.  With some caveats, it can be used
 interchangably with CFTreeRef, not that you'd necessarily want to given Core
 Foundation's obtuse calling syntax.
 
 If you've not used trees before, you should familarise yourself with a few concepts
 before using this class, as follows.
 
 Tree structures are made up of #nodes, each of which can have zero or one #parent node,
 and zero or more #child nodes.
 
 A node also has zero or more #sibling nodes - that is, those nodes which are also children
 of the node's parent.
 
 A node can only exist in one tree, and at only one place in that tree. 
 
 From any given node, we can move 'up' the tree via its parent, and its parent's
 parent, until we reach a node which has no parent.  For a given tree structure, there
 can be only one node with no parent, and this is referred to as the #root node.
 
 Similarly, a node with no children is referred to as a #leaf node.  There can be any
 number of leaf nodes in a tree structure.
 
 Keeping with the gardening metaphor, one can #prune subtrees (remove them entirely) or
#graft them (move them from one place in a tree to another, or even somewhere in another
             tree entirely).  Of course, moving a node moves all of its children at the same time, thus
 a node can be said to represent an entire subtree.
 
 The class TCUTree represents a single tree node, and holds a reference to an arbitrary
 other object, which is thus placed within a tree structure.
 
 Once a TCUTree instance has been created, it can be placed in a tree structure as described
 above, queried, and generally played with.
 
 Contrary to the usage of most of Foundation's collection classes, most of the methods
 on TCUTree do not act on the referenced object, but on the structure of the tree itself.
 One must explicitly ask a TCUTree for its contents via its #{-object} selector.
 Everything else is structural.
 
 %{It should be noted that, as this class is toll-free bridged outside of
     CoreFoundation, using undocumented hacks, there are no guarantees that this
     class will even make it past its +intialize method, let alone actually do what
         it's supposed to. Even the way we find the place to patch CoreFoundation isn't found in in the
         mach-o documentation. I wouldn't even #think of using it for delivered software
             unless you really, really enjoy debugging at a low level every time Apple update
             CoreFoundation...}
 
 %{It will only work on MacOS X / Darwin - no GNUStep functionality is planned,
     or even possible at the moment, unless the GNUStep people go mad and implement CoreFoundation.}
 
 Subclassing of this class is possible, but beware:  Don't try to cast from CFTree objects to a subclassed class unless you have subclassed without adding variables (and if you're doing that, why aren't you using a category?). "*/

/*""*/

#pragma mark -
#pragma mark Custom Toll-Free Bridging
- (CFTypeID) _cfTypeID {
    return CFTreeGetTypeID();
}

#pragma mark -
#pragma mark Memory Management
/*" Convenience constructor, returns an autoreleased instance of TCUTree referencing the
object passed in."*/
+ (id) treeWithObject:(id) object {
    return [[[TCUTree alloc] initWithObject:object] autorelease];
}

+ (id) treeWithContentsOfFile:(NSString*)file
{
    return [[[TCUTree alloc] initWithFile:file] autorelease];
}

- (id) copyWithZone: (NSZone *) zone {
    id newObject = [[[self class] alloc] initWithObject:[self object]];
    NSEnumerator * enumerator = [self childEnumerator];
    id child;
    
    while ((child = [enumerator nextObject]))
        [newObject addChild:[child copy]];
    
    return newObject;
}

- (void) encodeWithCoder: (NSCoder *) aCoder {
    // This one's easier
    [aCoder encodeObject:[self children] forKey:CODING_CHILDREN_KEY];
    [aCoder encodeObject:[self object] forKey:CODING_OBJECT_KEY];

}

- (id) initWithCoder: (NSCoder *) aCoder {
    id object = [aCoder decodeObjectForKey:CODING_OBJECT_KEY];
    if ((self = [self initWithObject:object])) {
        id childArray = [aCoder decodeObjectForKey:CODING_CHILDREN_KEY];
        NSEnumerator * enumerator = [childArray objectEnumerator];
        id aChild;
        
        while ((aChild = [enumerator nextObject])) {
            [self addChild:aChild];
        }
    }
    return self;
}

- (id) initWithDictionary:(NSDictionary*)dict
{
    NSMutableArray *allKeys = [[[dict allKeys] mutableCopy] autorelease];
    // We remove our private key from the list of keys...
    [allKeys removeObject:CODING_CHILDREN_KEY];

    id object = nil;
    if ([allKeys count] == 0) {
        // There is no item here, init with object won't like that...
        [NSException raise:NSInvalidArgumentException format:@"Dictionary don't hold enough values"];
        
    } else if ([allKeys count] == 1) {
        // There is only one item is there, this is our object
        object = [[[dict objectForKey:[allKeys objectAtIndex:0]] mutableCopy] autorelease];
    } else {
        // There is more that one object in there, we create a dictionary with these, and it'll be our object
        object = [NSMutableDictionary dictionaryWithObjects:[dict objectsForKeys:allKeys notFoundMarker:[NSNull null]]
                                                    forKeys:allKeys];
    }
    
    if ((self = [self initWithObject:object])) {
        id childArray = [dict objectForKey:CODING_CHILDREN_KEY];
        
        NSEnumerator * enumerator = [childArray objectEnumerator];
        id aChild;
        
        while ((aChild = [enumerator nextObject])) {
            id child = [[[TCUTree alloc] initWithDictionary:aChild] autorelease];
            [self addChild:child];
        }
    }
    return self;
}

// Disallow use of basic constructor
- (id) init
{
    [self autorelease];
    return nil;
}

/*" Designated initaliser.  Creates a 'root' tree object referencing the object passed in.

Note that use of the normal initialiser, #{-init}, is disallowed and will return nil.
"*/
- (id) initWithObject:(id)object
{
    if (!object) {
        [NSException raise:NSInvalidArgumentException format:@"Can't init a tree with nil"];
        return nil;
    }
    
    CFTreeContext defaultContext;
    
    defaultContext.version = 0;
    defaultContext.info = (void *)object;
    defaultContext.retain = CFRetain;
    defaultContext.release = CFRelease;
    defaultContext.copyDescription = CFCopyDescription;
    
    self = (TCUTree*) CFTreeCreate(NULL, &defaultContext);
    return self;
}

- (id) initWithFile:(NSString*)file
{
    id data = [NSData dataWithContentsOfFile:file];
    
    NSString *error = nil;
    
    id dict = [NSPropertyListSerialization propertyListFromData:data
                                               mutabilityOption:NSPropertyListMutableContainersAndLeaves
                                                         format:NULL
                                               errorDescription:&error];
    
    if (error != nil) {
        [error autorelease];
        [NSException raise:NSInvalidArgumentException format:error];
        
    }
    
    return [self initWithDictionary:dict];
}

#pragma mark -
#pragma mark Core Foundation Wrapper

/*"
Returns a pointer to the object passed in on creation.
 
 This method should be used with caution, if at all, on
 objects created using CoreFoundation calls rather than TCUTree methods.  This is
 because CoreFoundation can use any pointer, whereas we are restricting ourselves
 to objects.  Thus, if the value object is actually a straight 'C' pointer, we risk
 SEGV frenzy the instant we try to treat it as an ObjC object.
 "*/
- (id) object
{
    CFTreeContext context;
    CFTreeGetContext((CFTreeRef)self, &context);
    
    return (id)context.info;
}

/*" Returns the 'root' of the containing tree, or self if this tree has no parent "*/
- (TCUTree*) root {
    return (TCUTree*)CFTreeFindRoot((CFTreeRef)self);
}

/*" Find the parent of this tree, or nil if this tree has no parent. "*/
- (TCUTree*) parent {
    return (TCUTree*)CFTreeGetParent((CFTreeRef)self);
}

/*" Count of children for this tree "*/
- (unsigned) childCount {
    return CFTreeGetChildCount((CFTreeRef)self);
}

/*" First child of the tree, or nil if this tree is a leaf "*/
- (TCUTree*) firstChild {
    return (TCUTree*)CFTreeGetFirstChild((CFTreeRef)self);
}

/*" Returns the child at the given index.

Will raise NSInvalidArgumentException if the index is out of range.
"*/
- (TCUTree*) childAtIndex: (unsigned) index {
    if (index >= [self childCount])
        [NSException raise:NSInvalidArgumentException format:@"%@ : index %d beyond bounds (%d)", NSStringFromSelector(_cmd), index, [self childCount]];
    
    return (TCUTree*)CFTreeGetChildAtIndex((CFTreeRef) self, index);
}

/*" Returns the next sibling tree, or nil if the tree has no parent / is the last child of its parent. "*/
- (TCUTree*) nextSibling {
    return (TCUTree*)CFTreeGetNextSibling((CFTreeRef)self);
}

/*" Appends the given child at the beginning of the list of children "*/
- (void) prependChild: (TCUTree*) child {
    CFTreePrependChild((CFTreeRef)self, (CFTreeRef)child);
}

/*" Appends the given child at the end of the list of children "*/
- (void) addChild: (TCUTree*) child {
    CFTreeAppendChild((CFTreeRef)self, (CFTreeRef)child);
}

/*" Adds the given tree as a sibling, directly after this one in the parent's list of children.  Does nothing if this tree has no parent. "*/
- (void) appendSibling: (TCUTree*) sibling {
    CFTreeInsertSibling((CFTreeRef)self, (CFTreeRef)sibling);
}

/*" Remove this tree from its parent "*/
- (void) prune {
    CFTreeRemove((CFTreeRef)self);
}

/*" Removes all children from the tree, making it a leaf "*/
- (void) removeAllChildren {
    CFTreeRemoveAllChildren((CFTreeRef)self);
}

#pragma mark -
#pragma mark Additional Methods

/*" Returns an NSEnumerator instance that can be used to enumerate through the
children of this tree.

This only enumerates through the direct children of
the tree.  If recursive processing is required, the user will have to implement
it.

As with all the other collection classes, it is not safe to mutate the collection while enumerating.
"*/
- (NSEnumerator*) childEnumerator {
    return [[self children] objectEnumerator];
}

- (NSEnumerator*) reverseChildEnumerator {
    return [[self children] reverseObjectEnumerator];
}

/*" Returns true if this tree has no children, otherwise false "*/
- (BOOL) isLeaf {
    return [self childCount] == 0;
}

/*" Last child of the tree, or nil if this tree is a leaf. "*/
- (TCUTree*) lastChild {
    if ([self childCount])
        return [self childAtIndex:[self childCount]-1];
    else
        return nil;
}

/*" Returns an immutable array of all child trees. "*/
- (NSArray*) children {
    int index;
    NSMutableArray * array = [NSMutableArray array];
    
    for (index = 0; index < [self childCount]; index++)
        [array addObject:[self childAtIndex:index]];
    
    return [[array copy] autorelease];
}

/*" Search for child containment.
"*/
- (BOOL) containsChild: (TCUTree*) child recurse:(BOOL)recurse {
    if (child == nil) {
        [NSException raise:NSInvalidArgumentException format:@"Can't find a nil children"];
    }
    
    if (!recurse)
        return [[self children] containsObject:child];
    else {
        if ([self isLeaf])
            return [self isEqual:child];
        else {
            NSEnumerator * enumerator = [self childEnumerator];
            id thisChild;
            BOOL containsChild = [self isEqual:child];
            
            while ((thisChild = [enumerator nextObject]) && !containsChild) {
                containsChild = [thisChild containsChild:child recurse:YES];
            }
            return containsChild;
        }
    }
    return NO;
}

/*" Returns the index of the passed in child, or NSNotFound if it's not contained "*/
- (unsigned) indexOfChild: (TCUTree*) child {
    return [[self children] indexOfObject:child];
}

/*" Returns the previous sibling tree, or nil if the tree has no parent / is the first child of its parent. "*/
- (TCUTree*) previousSibling {
    id parent = [self parent];
    if (parent) {
        unsigned index = [parent indexOfChild:self];
        if (index > 0)
            return (TCUTree*)[parent childAtIndex:index-1];
    }
    return nil;
}

/*" Inserts the given child at the given index, raises NSInvalidArgumentException if the index is out of range "*/
- (void) addChild: (TCUTree*) child atIndex: (unsigned) index {
    if ((index < 0) || (index > [self childCount]))
        [NSException raise:NSInvalidArgumentException format:@"Index %d out of bounds (%d)", index, [self childCount]];
    if (index == 0) {
        [self prependChild:child];
    } else if (index == [self childCount]) {
        [self addChild:child];
    } else {
        [[self childAtIndex:index] prependSibling:child];
    }
}

/*" Remove the given child, if it's contained as a direct child of this tree "*/
- (void) removeChild: (TCUTree*) child {
    if ([self containsChild:child recurse:NO])
        [child prune];
}

/*" Remove the child at the given index, raises NSInvalidArgumentException if the index is out of range "*/
- (void) removeChildAtIndex: (unsigned) index {
    if ((index < 0) || (index > [self childCount]))
        [NSException raise:NSInvalidArgumentException format:@"Index %d out of bounds (%d)", index, [self childCount]];
    [[self childAtIndex:index] prune];
}

/*" Adds the given tree as a sibling, directly before this one in the parent's list of children.  Does nothing if this tree has no parent. "*/
- (void) prependSibling: (TCUTree*) sibling {
    id parent = [self parent];
    if (parent) {
        id previousSibling = [self previousSibling];
        if (previousSibling)
            [previousSibling appendSibling:sibling];
        else
            [parent prependChild:sibling];
    }
}

/*" Removes this tree from its current parent, if necessary, then adds it to the end of the child list of the given tree, NSInvalidArgumentException if the destination tree is contained somewhere within self's subtree "*/
- (void) graftOntoTree: (TCUTree*) tree {
    if (![self containsChild:tree recurse:YES]) {
        [self prune];
        [tree addChild:self];
    } else {
        [NSException raise:NSInvalidArgumentException format:@"Cannot graft an item onto itself or a subbranch"];
    }
}

/*" Removes this tree from its current parent, if necessary, then adds it to the child list of the given tree, at the index given, raises NSInvalidArgumentException if the index is out of range or the destination tree is contained somewhere within self's subtree "*/
- (void) graftOntoTree: (TCUTree*) tree atIndex: (unsigned) index {
    if (index <= [tree childCount]) {
        if (![self containsChild:tree recurse:YES]) {
            [self prune];
            [tree addChild:self atIndex:index];
        } else {
            [NSException raise:NSInvalidArgumentException format:@"Cannot graft an item onto itself or a subbranch"];
        }
    } else {
        [NSException raise:NSInvalidArgumentException format:@"range %d out of range (%d)", index, [tree childCount]];
    }
}

/*" Recursively search for a subtree containing a value object equal to object.

Equality of value objects is determined using #{-isEqual:}"*/
- (TCUTree*) subtreeContainingObject:(id)object {
    id subtree = [[self object] isEqual:object] ? self : nil;
    NSEnumerator * enumerator = [self childEnumerator];
    id child;
    
    while ((!subtree) && (child = [enumerator nextObject])) {
        subtree = [child subtreeContainingObject:object];
    }
    return subtree;
}

- (NSDictionary*) dictionaryRepresentation
{
    NSMutableArray  *children = [NSMutableArray array];
    
    NSEnumerator    *childEnum = [self childEnumerator];
    id child;
    while ((child = [childEnum nextObject])) {
        [children addObject:[child dictionaryRepresentation]];
    }
    
    return [NSDictionary dictionaryWithObjectsAndKeys:
        children,       CODING_CHILDREN_KEY,
        [self object],  CODING_OBJECT_KEY,
        nil];
}

- (BOOL) writeToFile:(NSString*)file  atomically:(BOOL)atomically
{
    NSString    *error = nil;
    NSData      *data = [NSPropertyListSerialization dataFromPropertyList:[self dictionaryRepresentation]
                                                                   format:NSPropertyListXMLFormat_v1_0
                                                         errorDescription:&error];
    
    if (error) {
        [error autorelease];
        [NSException raise:NSInvalidArgumentException format:error];
        return NO;
    }
    
        return [data writeToFile:file atomically:atomically];
}

@end


#pragma mark -
@implementation TCUTree (NSOutlineViewDataSource)

- (int)outlineView:(NSOutlineView *)outlineView numberOfChildrenOfItem:(id)item
{
    if (item)
        return  [item childCount];
    else
        return [[outlineView dataSource] childCount];
}

- (BOOL)outlineView:(NSOutlineView *)outlineView isItemExpandable:(id)item
{
    return ![item isLeaf];
}

- (id)outlineView:(NSOutlineView *)outlineView child:(int)index ofItem:(id)item
{
    if (item)
        return  [item childAtIndex:index];
    else
        return [[outlineView dataSource] childAtIndex:index];
}

- (id)outlineView:(NSOutlineView *)outlineView objectValueForTableColumn:(NSTableColumn *)tableColumn byItem:(id)item
{
    return [[item object] valueForKey:[tableColumn identifier]];
}

- (void)outlineView:(NSOutlineView *)outlineView setObjectValue:(id)object forTableColumn:(NSTableColumn *)tableColumn byItem:(id)item
{
    [[item object] setValue:object forKey:[tableColumn identifier]];
}


/*- (id)outlineView:(NSOutlineView *)outlineView itemForPersistentObject:(id)object
{
    
}

- (id)outlineView:(NSOutlineView *)outlineView persistentObjectForItem:(id)item
{
    
}*/

/*
- (void)outlineView:(NSOutlineView *)outlineView sortDescriptorsDidChange:(NSArray *)oldDescriptors
{
     
}*/


- (BOOL)outlineView:(NSOutlineView *)olv writeItems:(NSArray*)items toPasteboard:(NSPasteboard*)pboard
{
    [pboard declareTypes:[NSArray arrayWithObjects: TreePasteboardType, nil] owner:self];
    
    NSMutableArray  *convertedArray = [[NSMutableArray alloc] init];
    
    NSEnumerator    *itemEnum = [items objectEnumerator];
    id item;
    while ((item = [itemEnum nextObject])) {
        [convertedArray addObject:[item dictionaryRepresentation]];
    }
    
    NSString    *error = nil;
    
    NSData      *data = [NSPropertyListSerialization dataFromPropertyList:convertedArray
                                                                   format:NSPropertyListBinaryFormat_v1_0
                                                         errorDescription:&error];
    
    if (error) {
        [error autorelease];
        [NSException raise:NSInternalInconsistencyException format:error];
        return NO;
    }
    
    [pboard setData:data forType:TreePasteboardType];
    return YES;
}

- (NSDragOperation)outlineView:(NSOutlineView*)olv validateDrop:(id <NSDraggingInfo>)info proposedItem:(id)item proposedChildIndex:(int)index
{
    NSArray *acceptedType = [NSArray arrayWithObject: TreePasteboardType];
    
    // Check to make sure we don't allow a node to be inserted into one of its descendants!
    if ([[info draggingPasteboard] availableTypeFromArray:acceptedType] != nil) {
        NSData  *draggedData = [[info draggingPasteboard] dataForType:TreePasteboardType];
        NSArray *draggedNodes = [NSPropertyListSerialization propertyListFromData:draggedData
                                                                 mutabilityOption:NSPropertyListImmutable
                                                                           format:NULL
                                                                 errorDescription:NULL];
        
        NSEnumerator    *draggedEnum = [draggedNodes objectEnumerator];
        id               dragged;
        while ((dragged = [draggedEnum nextObject])) {
            
            TCUTree *draggedNode = [[olv dataSource] subtreeContainingObject:[dragged objectForKey:CODING_OBJECT_KEY]];
            
            // item == nil it when we're asked for a top-level drop
            if (item != nil && [draggedNode containsChild:item recurse:YES])
                return NSDragOperationNone;
        }
    }
    
    // Set the item and child index in case we computed a retargeted one.
    [olv setDropItem:item dropChildIndex:index];
    
    return NSDragOperationGeneric;
}

- (BOOL)outlineView:(NSOutlineView*)olv acceptDrop:(id <NSDraggingInfo>)info item:(id)item childIndex:(int)index
{
    index = (index == NSOutlineViewDropOnItemIndex ? [item childCount] : index);
    
    NSArray *acceptedType = [NSArray arrayWithObject: TreePasteboardType];
    
    // Check to make sure we don't allow a node to be inserted into one of its descendants!
    if ([[info draggingPasteboard] availableTypeFromArray:acceptedType] != nil) {
        NSData  *draggedData = [[info draggingPasteboard] dataForType:TreePasteboardType];
        NSArray *draggedNodes = [NSPropertyListSerialization propertyListFromData:draggedData
                                                                 mutabilityOption:NSPropertyListImmutable
                                                                           format:NULL
                                                                 errorDescription:NULL];
        
        NSEnumerator    *draggedEnum = [draggedNodes objectEnumerator];
        id               dragged;
        while ((dragged = [draggedEnum nextObject])) {
            TCUTree *draggedNode = [[olv dataSource] subtreeContainingObject:[dragged objectForKey:CODING_OBJECT_KEY]];
            
            if (item == nil) {
                [draggedNode graftOntoTree:[olv dataSource] atIndex:index];
            } else
                [draggedNode graftOntoTree:item atIndex:index];
        }
    }
    
    [olv reloadData];
    
    return YES;
}

//- (NSArray *)outlineView:(NSOutlineView *)olv namesOfPromisedFilesDroppedAtDestination:(NSURL *)dropDestination forDraggedItems:(NSArray *)items;
@end
